#include <iostream>
#include <vector>

using namespace std;

#define ITEMS 4
int w[] = {2,3,4,5};
int v[] = {3,4,5,6};

vector<int> Find(int weight)
{

    int dp[5][20];

    vector<int> rtn;

    for (int i = 0; i <= weight; i++)

        dp[0][i] = 0;



    for (int i = 1; i <= ITEMS; i++) {

        dp[i][0] = 0;

        for (int j = 1; j <= weight; j++) {

            if (w[i-1] <= j){

                if (v[i-1] + dp[i-1][j-w[i-1]] > dp[i-1][j])

                    dp[i][j] = v[i-1] + dp[i-1][j-w[i-1]];

                else

                    dp[i][j] = dp[i-1][j];

            } else {

                dp[i][j] = dp[i-1][j];

            }

        }

    }



    for (int i = 0; i <= ITEMS; i++) {

        cout << endl;

        for (int j = 0; j <= weight; j++) {

            cout << dp[i][j] << " " ;

        }

    }



    //output the soluton

    int i_ = 4;

    int j = weight;

    int test;

    while(j > 0) {

        if (dp[i_][j] != dp[i_-1][j]) {

            rtn.push_back(i_);

            j -= w[i_-1];

               i_ -= 1;

        }

        else

        {

            i_ -= 1;

            test = 6;

        }

    }

    cout << endl;
    return rtn;

}





int main()

{

    int weight = 5;

    vector<int> output = Find(weight);
    for (int i = 0; i < output.size(); i++)
        cout << output[i] << " ";
    cout << endl;
}
